Skip to main content

Binary Tree Level Order Traversal

Question​

What is the most efficient way to traverse a binary tree level-by-level and output the nodes in each level in the same order they appear?

Example 1
Input: 
   3
  / \
 9  20
   /  \
  15   7

Output: 
[
  [3],
  [9,20],
  [15,7]
]

Solution​

all//Binary Tree Level Order Traversal.py


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root):
        if root is None:
            return []

        result = []
        current_level = [root]
        while current_level:
            next_level = []
            level_vals = []
            for node in current_level:
                level_vals.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            result.append(level_vals)
            current_level = next_level
        return result